const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定一个单链表的头节点head
// 要求，将该单链表进行反转，可以迭代或者递归地反转链表

// 思路1，双指针法
// pre，cur，temp分别指向上一个节点，当前节点，下一个待处理节点
// 每轮遍历中，cur.next = pre ,然后更新pre为cur，更新cur 为temp，直到cur为null，此时pre为首节点

function reverseList(head) {
    let pre = null
    let cur = head
    let temp = null
    while (cur) {
        // 先把cur的next存下，下一轮处理它
        temp = cur.next
        // 把cur的next指向上一个节点
        cur.next = pre
        // 把cur作为pre，用作下一轮处理
        pre = cur
        // 把cur更新为temp，进行下一轮处理
        cur = temp
    }
    return pre
}

let node = new LinkedList([1, 2, 3, 4])
console.log(reverseList(node.head));

// 思路2，递归法
// 和双指针遍历的思路一致，从前往后遍历
function reverseList2(head) {
    function reverse(pre, cur) {
        // cur为null时，pre是新的头节点
        if (!cur) {
            return pre
        }   
        let temp =cur.next
        cur.next = pre
        return reverse(cur, temp)
    }
    return reverse(null, head)
}
let node2 = new LinkedList([1, 2, 3, 4])
console.log(reverseList2(node2.head));

// 思路3，递归法，从后往前
function reverseList3(head) {
    if (!head || !head.next) {
        return head
    }
    // 先不断递归，找到最后一个节点
    let res = reverseList3(head.next)
    // head.next就是head后面的节点，后面的节点的next指向head，反转
    head.next.next = head
    // 把head的next置空，留给下一轮归并的时候处理
    head.next = null
    return res
}

let node3 = new LinkedList([1, 2, 3, 4])
console.log(reverseList3(node3.head));